/**
 * @file luogu/2023/main.cpp
 * @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
 * @brief 区间加，区间乘，询问区间和
 *
 * 带懒标记的线段树
 *
 * 注意：因为乘的运算级别比加高，所以在做加法是不用管乘法，在做乘法时要管加法。
 * @see <https://www.luogu.com.cn/record/75296135> 3.83s/13.15MB/2.62KB C++17 O2
 * @version 1.0
 * @date 2022-05-07
 *
 * @copyright Copyright (c) 2022
 *
 **/

#include <bits/stdc++.h>
using namespace std;
const int N = 200007;
typedef long long ll;
int n, q, L, R, op;
ll k, P, a[N];
struct SegTree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid (l + r >> 1)
  ll sum[N << 2], mul[N << 2], add[N << 2];
  void pushdown(int rt, int l, int r) {
    if (mul[rt] == 1 && add == 0) {
      return;  // 没有标记
    }
    if (l != r) {
      mul[ls] = mul[ls] * mul[rt] % P;
      mul[rs] = mul[rs] * mul[rt] % P;

      add[ls] = (add[ls] * mul[rt] % P + add[rt]) % P;
      add[rs] = (add[rs] * mul[rt] % P + add[rt]) % P;
    }
    sum[rt] = (sum[rt] * mul[rt] % P + add[rt] * (r - l + 1) % P) % P;

    mul[rt] = 1, add[rt] = 0;
  }
  void pushup(int rt) { sum[rt] = sum[ls] + sum[rs]; }
  void build(int rt, int l, int r) {
    mul[rt] = 1, add[rt] = 0;
    if (l == r) {
      sum[rt] = a[l];
      return;
    }
    build(ls, l, mid), build(rs, mid + 1, r);
    pushup(rt);
  }
  ll query_sum(int rt, int l, int r) {
    pushdown(rt, l, r);
    if (L <= l && r <= R) {
      return sum[rt];
    }
    ll ret = 0;
    if (L <= mid) ret = (ret + query_sum(ls, l, mid)) % P;
    if (R >= mid + 1) ret = (ret + query_sum(rs, mid + 1, r)) % P;
    return ret;
  }
  void range_add(int rt, int l, int r) {
    pushdown(rt, l, r);
    if (L <= l && r <= R) {
      add[rt] = (add[rt] + k) % P;
      return;
    }
    if (L <= mid) range_add(ls, l, mid);
    if (R >= mid + 1) range_add(rs, mid + 1, r);
    pushdown(ls, l, mid), pushdown(rs, mid + 1, r);
    pushup(rt);
  }
  void range_mul(int rt, int l, int r) {
    pushdown(rt, l, r);
    if (L <= l && r <= R) {
      // 加法和乘法都要乘一个 k
      mul[rt] = mul[rt] * k % P;
      add[rt] = add[rt] * k % P;
      return;
    }
    if (L <= mid) range_mul(ls, l, mid);
    if (R >= mid + 1) range_mul(rs, mid + 1, r);
    pushdown(ls, l, mid), pushdown(rs, mid + 1, r);
    pushup(rt);
  }
#undef mid
#undef ls
#undef rs
} ST;
int main() {
  cin >> n >> P;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  ST.build(1, 1, n);
  int tc;
  cin >> tc;
  while (tc--) {
    cin >> op;
    if (op == 1) {
      cin >> L >> R >> k;
      ST.range_mul(1, 1, n);
    } else if (op == 2) {
      cin >> L >> R >> k;
      ST.range_add(1, 1, n);
    } else {
      cin >> L >> R;
      cout << ST.query_sum(1, 1, n) << endl;
    }
  }
}
